//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 
//
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：[["a"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
//
// Related Topics 字符串 动态规划 回溯 👍 1705 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PalindromePartitioning {
    public static void main(String[] args) {
        Solution solution = new PalindromePartitioning().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 乍一看和78子集很像，只不过要多加一个判断是否是回文传
         * 但是又不像，他要的是切割方式并不是子串是回文串
         * @param s
         * @return
         */
        public List<List<String>> partition(String s) {
            int n = s.length();
            char[] arr = s.toCharArray();
            boolean[][] f = new boolean[n][n];
            //动态规划预先知道i..j是否是回文串
            for (int j = 0; j < n; j++) {
                for (int i = j; i >= 0; i--) {
                    if (i==j) {
                        f[i][j] = true;
                    }
                    else {
                        if (j-i  == 1) {
                            f[i][j] =  arr[i] == arr[j];
                        }else {
                            f[i][j] = arr[i] == arr[j] && f[i + 1][j - 1];
                        }
                    }
                }
            }
            List<List<String>> result = new ArrayList<>();

            //开始爆搜
            dfs(s,0,result,new ArrayList<>(),f);
            return result;
        }

        /**
         *
         * @param s
         * @param n
         * @param result
         * @param list 动态的保存每一层的list
         * @param f
         */
        private void dfs(String s,int n,List<List<String>> result,List<String> list,boolean[][] f){
            int num = s.length();
            if (n == num) result.add(new ArrayList<>(list)); //切割到了最后一个 说明本次切割方法已经完成

            for (int i = n; i < num; i++) {
                //如果当前层数的前n个是回文串，就爆搜下一层
                if (f[n][i]){
                    list.add(s.substring(n,i+1));
                    dfs(s,i+1,result,list,f);
                    list.remove(list.size()-1);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}